import org.w3c.dom.Node;

import java.util.LinkedList;
import java.util.List;

public class LIST {
    public static void main(String[] args) {
//        boolean add(E e)                          尾插 e
//        void add(int index, E element)            将 e 插入到 index 位置
//        boolean addAll(Collection<? extends E> c) 尾插 c 中的元素
//        E remove(int index)                       删除 index 位置元素
//        boolean remove(Object o)                  删除遇到的第一个 o
//        E get(int index)                          获取下标 index 位置元素
//        E set(int index, E element)               将下标 index 位置元素设置为 element
//        void clear()                              清空
//        boolean contains(Object o)                判断 o 是否在线性表中
//        int indexOf(Object o)                     返回第一个 o 所在下标
//        int lastIndexOf(Object o)                 返回最后一个 o 的下标
//        List<E> subList(int fromIndex, int toIndex)截取部分list
        List<Integer> list = new LinkedList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(6);
        list.add(4);
        list.add(5);
        list.add(6);
        System.out.println(list);
        // 在起始位置插入0
        list.add(0, 0);
        // add(index, elem): 在index位置插入元素elem

        System.out.println(list);

        list.remove(1);
        // remove(index): 删除index位置的元素

        System.out.println(list);
        // contains(elem): 检测elem元素是否存在，如果存在返回true，否则返回false

        if(!list.contains(1)){
            list.add(0, 1);
        }

        list.add(1);
        System.out.println(list);

        System.out.println(list.indexOf(1));
        // indexOf(elem): 从前往后找到第一个elem的位置

        System.out.println(list.lastIndexOf(1));
        // lastIndexOf(elem): 从后往前找第一个1的位置

        int elem = list.get(0);
        // get(index): 获取指定位置元素
        System.out.println(elem);

        list.set(0, 100);
        // set(index, elem): 将index位置的元素设置为elem
        System.out.println(list);

        // subList(from, to): 用list中[from, to)之间的元素构造一个新的LinkedList返回
        List<Integer> copy = list.subList(0, 3);
        System.out.println(list);
        System.out.println(copy);

        list.clear();
        // 将list中元素清空



    }
    static class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) {
          this.val = val;
      }
//      ListNode(int val, ListNode next) {
//          this.val = val; this.next = next;
//      }
  }
  //移除头节点
   // 给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
    class Solution {
        public ListNode removeElements(ListNode head, int val) {
            //如果头节点为空,范围null
            if(head==null){
                return head;
            }
            //cur的值为删除节点的前一个
            ListNode cur=head;
            //要删除的节点
            ListNode del=head.next;

            while(del!=null){
                //如果删除的节点的值等于所求值进入循环
                if(del.val==val){
                    //用cur的next值等于删除节点的next值,然后删除节点后移
                    //注意二者不可调换,否则进入死循环
                    cur.next=del.next;
                    del=del.next;
                }
                else{
                    //正常向下循环
                    del=del.next;
                    cur=cur.next;
                }
            }
            //判断头节点
            if(head.val==val){
                head=head.next;
            }
            return head;
        }
    }
    //反转链表
    //给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
    class Solution1 {
        public ListNode reverseList(ListNode head) {
            //判断头节点
            if(head==null){
                return head;
            }

            if(head.next==null){
                return head;
            }

            //设置一个空链表reversal
            ListNode reversal=null;
            ListNode cur=head;

            while(cur!=null){
                //middle为头节点的下一个节点,用于存储数值
                ListNode middle=cur.next;

                //最开始的cur的值为reversal的尾节点
                //若1 2 3 4 5 6 六个数
                //经过一次循环,reversal中的数为 1
                cur.next=reversal;

                //把reversal的值挪到最前面
                //若经过两次循环reversal中有 2 1 但是reversal纸箱的是 1
                //利用下述代码可以把它挪到前面
                reversal=cur;
                cur=middle;

            }
            return reversal;
        }
    }

     //链表的中间节点
     //给你单链表的头结点 head ，请你找出并返回链表的中间结点。
     //如果有两个中间结点，则返回第二个中间结点。
    class Solution3 {
        public ListNode middleNode(ListNode head) {
            ListNode fast=head;
            ListNode slow=head;
            //利用快慢指针进行寻找,当快指针到头时,慢指针到中间
            //因为二者相差2倍
            while(fast!=null&&fast.next!=null){
                fast=fast.next.next;
                slow=slow.next;
            }
            return slow;

        }
    }

    //合并两个有序链表
    //将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
    class Solution4 {
        public ListNode mergeTwoLists(ListNode list1, ListNode list2) {

            if(list1==null&&list2==null){
                return list1;
            }

            if(list1!=null&&list2==null){
                return list1;
            }

            if(list1==null&&list2!=null){
                return list2;
            }

            ListNode head = new ListNode(0);
            ListNode pre = head;

            while(list1 != null && list2 != null){
                //判断两个链表中的数值大
                if(list1.val <= list2.val){
                    pre.next = list1;
                    list1 = list1.next;
                }else {
                    pre.next = list2;
                    list2 = list2.next;
                }
                pre = pre.next;
            }
            //因为最开始的头节点的设定为0
            if(head.val==0){
                head=head.next;
            }
            //三目运算符,list1为空吗,为空执行list2,不为空执行list1
            pre.next = list1 == null ? list2 : list1;
            return head;
        }
    }

//    判断回文数
//    对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。
//
//    给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。
//
//    测试样例：
//            1->2->2->1
//    返回：true
    public class PalindromeList {
        public boolean chkPalindrome(ListNode A) {
            // write code here
            ListNode slow=A;
            ListNode fast=A;
            //slow为中间节点
            //fast和fast.next的位置不能调换!!!!!
            while(fast!=null&&fast.next!=null){
                slow=slow.next;
                fast=fast.next.next;
            }
            //对后半部分进行逆置操作
            ListNode slow2=fanzhuan(slow);
//        ListNode node=A;

            while(slow2!=null&&A!=null){
                if(slow2.val!=A.val){
                    return false;
                }else{
                    slow2=slow2.next;
                    A=A.next;
                }
            }
            return true;
        }
        public ListNode fanzhuan(ListNode A){
            if(A==null){
                return null;
            }
            ListNode new1=null;
            ListNode node=A;
            ListNode node2=A.next;

            while(node!=null){
                node.next=new1;
                new1=node;
                node=node2;
                if(node2!=null){
                    node2=node2.next;
                }
            }

            return new1;

        }
    }




















}




